package com.leetcode.partition3;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/9/8 15:32
 */
@SuppressWarnings("all")
public class LC239滑动窗口最大值 {

    public static int[] maxSlidingWindow(int[] nums, int k) {
//        return slidingWindow(nums, k);
//        return priorityQueue(nums, k);
        return monotonicQueue(nums, k);
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
//        int[] nums = {1, -1};
        int k = 3;
        System.out.println(Arrays.toString(maxSlidingWindow(nums, k)));
    }

    private static int[] monotonicQueue(int[] nums, int k) {
        if (nums == null || nums.length < 2) return nums;
        List<Integer> answer = new ArrayList<>();
        //双向队列，单调队列只包含当前窗口区中的最大值
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            //判断对头是否已经滑出窗口，且要求left指针在窗口内，窗口区[i-k+1, i]
            if (!queue.isEmpty() && queue.peekFirst() < i - k + 1) queue.pollFirst();
            //要保证当前队列的数据是单调递减的
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) queue.pollLast();
            queue.addLast(i);
            if (i >= k - 1) answer.add(nums[queue.peekFirst()]);
        }
        return answer.stream().mapToInt(val -> val).toArray();
    }

    private static int[] priorityQueue(int[] nums, int k) {
        int[] answer = new int[nums.length - k + 1];
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        int left = 0, right, index = 0;
        for (int i = 0; i < k; i++) heap.add(nums[i]);
        int currentMax = heap.peek();
        answer[index++] = currentMax;
        for (right = k; right < nums.length; right++, left++) {
            heap.remove(nums[left]);
            heap.add(nums[right]);
            answer[index++] = heap.peek();
        }
        return answer;
    }

    private static int[] slidingWindow(final int[] nums, int k) {
        int[] answer = new int[nums.length - k + 1];
        int left = 0, right, currentMax = nums[0], index = 0;
        for (right = 0; right < k; right++) currentMax = Math.max(currentMax, nums[right]);
        answer[index++] = currentMax;
        for (right = k; right < nums.length; right++, left++) {
            if (nums[left] == currentMax) {             //从滑动窗口出去的是最大值
                currentMax = Integer.MIN_VALUE;
                for (int i = left + 1; i <= right; i++) {       //重新选定最大值
                    if (nums[i] > currentMax) currentMax = nums[i];
                }
            } else {
                currentMax = Math.max(currentMax, nums[right]);
            }
            answer[index++] = currentMax;
        }
        return answer;
    }
}
